home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 22 / Cream of the Crop 22.iso / program / ctlib100.zip / INSTALL.LZH / CTBTREES.INT < prev    next >
Text File  |  1996-10-12  |  7KB  |  164 lines
  1. {**************************************************************************}
  2. {*  BitSoft Development, L.L.C.                                           *}
  3. {*  Copyright (C) 1995, 1996 BitSoft Development, L.L.C.                  *}
  4. {*  All rights reserved.                                                  *}
  5. {*  BTree objects unit                                                    *}
  6. {*  Version 1.2.0                                                         *}
  7. {**************************************************************************}
  8.  
  9. unit ctBTrees;
  10.  
  11. {$X+,B-}
  12.  
  13. interface
  14.  
  15. uses Objects,
  16.      {$ifdef ver60} BsdVer60, {$endif}
  17.      Containr, ctTrees, ctStacks;
  18.  
  19. type
  20.   PmWayNode = ^TmWayNode;
  21.   TmWayNode = object(TNode)
  22.       ID : LongInt;
  23.       Owner : Pointer;
  24.       Count : Word;
  25.       Data : PChar;
  26.       Modified : Boolean;
  27.     constructor Init (AOwner : Pointer);
  28.     destructor Done; virtual;
  29.     procedure AtCopyBlock(Index, SourceIndex : Word; SourceNode : PmWayNode;
  30.       ItemCount : Word; Larger : Boolean);
  31.     procedure AtDelete(Index: Word; Larger : Boolean);
  32.     procedure AtDeleteBlock(Index, ItemCount : Word; Larger : Boolean);
  33.     procedure AtInsert(Index : Word; Item : Pointer; Subtree : LongInt;
  34.       Larger : Boolean);
  35.     function AtItem (Index : Word) : Pointer; virtual;
  36.     procedure AtPutItem (Index : Word; Item : Pointer); virtual;
  37.     procedure AtPutSubTree (Index : Word; SubTree : LongInt);
  38.     function AtSubTree (Index : Word) : LongInt;
  39.     procedure FreeAll; virtual;
  40.     procedure Insert (Item : Pointer; ChildNode : LongInt);
  41.     function IsFull : Boolean;
  42.     function GetKey(Item : Pointer) : Pointer; virtual;
  43.     function LoadData (AOffset : LongInt): Boolean; virtual;
  44.     function Search (Key : Pointer; var Index : Word) : Boolean; virtual;
  45.     function StoreData: Boolean; virtual;
  46.   end;  { TmWayNode }
  47.  
  48. type
  49.   PBaseBTree = ^TBaseBTree;
  50.   TBaseBTree = object(TStreamTree)
  51.       DataSize : Word;
  52.       NodeDataSize : Word;
  53.       MaxItems : Word;
  54.       CurrentNode : PmWayNode;
  55.       ParentStack : PArrayStack;
  56.       ChildIndex : LongInt;
  57.       FreeNodes : LongInt;
  58.       Version : Word;
  59.       TempItem : Pointer;
  60.       NodeBuffer : PCollection;
  61.       NodeBufferSize : LongInt;
  62.     constructor Init (AStream : PStream; ADegree, ADataSize, ANodeDataSize,
  63.       FileVersion : Word; ANodeBufferSize : LongInt);
  64.     constructor Open (AStream : PStream; ANodeBufferSize : LongInt);
  65.     destructor Done; virtual;
  66.     procedure AgeNode(Node : PmWayNode);
  67.     procedure ClearStack;
  68.     function Concatenate : Boolean;
  69.     function CopyItem(Item, Dest : Pointer) : Pointer; virtual;
  70.     function Degree : Word; virtual;
  71.     procedure Flush; virtual;
  72.     procedure FreeItem (Item : Pointer); virtual;
  73.     function GetNewNode : PmWayNode;
  74.     procedure GetNode (ID : LongInt);
  75.     function ItemPut (OldItem, NewItem : Pointer) : Boolean; virtual;
  76.     function ItemsMatch(Item1, Item2 : Pointer) : Boolean; virtual;
  77.     function KeyOf(Item : Pointer) : Pointer; virtual;
  78.     function NewNode : PmWayNode; virtual;
  79.     function NodeStoredSize : Word; virtual;
  80.     procedure PopNode;
  81.     procedure PushNode (ChildNode : LongInt; AChildIndex : Word);
  82.     procedure Redistribute(Source, Target, Parent : PmWayNode; SplitIndex,
  83.       ItemsToMove : Word; MoveToLeft : Boolean);
  84.     function RedistributeEmpty : Boolean;
  85.     function RedistributeFull (Item : Pointer) : Boolean;
  86.     procedure ReleaseNode (Node : PmWayNode);
  87.     function Split(var Item : Pointer; var ChildNode : LongInt) : Boolean;
  88.     procedure Update;
  89.   end; { TBaseBTree }
  90.  
  91. const
  92.   TBTreeSig : array [0..6] of Char = 'ctBTree';
  93.  
  94. const
  95.   TBTreeVer = $0100;
  96.  
  97. type
  98.   PBTree = ^TBTree;
  99.   TBTree = object(TBaseBTree)
  100.     constructor Init (ADegree, ADataSize : Word; AStream : PStream;
  101.       ABufferSize : LongInt);
  102.     constructor Open (AStream : PStream; ABufferSize : LongInt);
  103.     destructor Done; virtual;
  104.     function Delete (Item : Pointer) : Boolean; virtual;
  105.     function DeleteAll : Boolean; virtual;
  106.     function DeleteAllThat (Test: Pointer): Boolean;  virtual;
  107.     function Find (Key : Pointer; var Hits : LongInt) : Boolean;
  108.       virtual;
  109.     function FindThat (Key, Test : Pointer; var Hits : LongInt) :
  110.       Boolean; virtual;
  111.     function First : Pointer; virtual;
  112.     function FirstThat (Test : Pointer) : Pointer; virtual;
  113.     function ForEach (Action: Pointer): Boolean; virtual;
  114.     function ForEachThat (Test, Action : Pointer): Boolean; virtual;
  115.     function FreeAll : Boolean; virtual;
  116.     function FreeAllThat (Test: Pointer): Boolean; virtual;
  117.     function Height : Word; virtual;
  118.     function Insert (Item : Pointer) : Boolean; virtual;
  119.     function ItemReplace (OldItem, NewItem : Pointer) : Boolean; virtual;
  120.     function KeyFirst (Key : Pointer) : Pointer; virtual;
  121.     function KeyLast (Key : Pointer) : Pointer; virtual;
  122.     function Last : Pointer; virtual;
  123.     function LastThat(Test : Pointer) : Pointer; virtual;
  124.     function Next (Item : Pointer) : Pointer; virtual;
  125.     function NextThat(Test : Pointer; Item : Pointer) : Pointer; virtual;
  126.     function Prev (Item : Pointer) : Pointer; virtual;
  127.     function PrevThat(Test : Pointer; Item : Pointer) : Pointer; virtual;
  128.   private
  129.       DuplicatesStack : PArrayStack;
  130.     function LocateItem (Item : Pointer; var Index : Word) : Boolean;
  131.     function LocateFirst (Key : Pointer; var Index : Word) : Boolean;
  132.     function LocateLast (Key : Pointer; var Index : Word) : Boolean;
  133.     procedure ReadHeader; virtual;
  134.     function ValidSignature (ASignature : PChar) : Boolean;
  135.     function ValidVersion (AVersion : Word) : Boolean;
  136.     procedure WriteHeader; virtual;
  137.   end;  { TBTree }
  138.  
  139. type
  140.   PObjectBTree = ^TObjectBTree;
  141.   TOBjectBTree = object(TBTree)
  142.     constructor Init (ADegree, ADataSize : Word; AStream : PStream;
  143.       ABufferSize : LongInt);
  144.     procedure FreeItem (Item : Pointer); virtual;
  145.     function GetItem (var S : TStream) : Pointer; virtual;
  146.     function NewNode : PmWayNode; virtual;
  147.     procedure PutItem (var S : TStream; Item : Pointer); virtual;
  148.   private
  149.     function NodeStoredSize : Word; virtual;
  150.   end; { TObjectBTree }
  151.  
  152. type
  153.   PmWayObjectNode = ^TmWayObjectNode;
  154.   TmWayObjectNode = object(TmWayNode)
  155.     function AtItem (Index : Word) : Pointer; virtual;
  156.     procedure AtPutItem (Index : Word; Item : Pointer); virtual;
  157.     procedure FreeAll; virtual;
  158.     function LoadData (AOffset : LongInt): Boolean; virtual;
  159.     function StoreData: Boolean; virtual;
  160.   end; { TmWayObjectNode }
  161.  
  162. implementation
  163. end.
  164.